package com.example.array;

/**
 * 给定M×N矩阵，每一行、每一列都按升序排列，请编写代码找出某元素。
 * <p>
 * 矩阵示例如下
 * [[1,   4,  7, 11, 15],
 *  [2,   5,  8, 12, 19],
 *  [3,   6,  9, 16, 22],
 *  [10, 13, 14, 17, 24],
 *  [18, 21, 23, 26, 30]]
 * <p>
 * 给定 target = 5，返回 true。
 * <p>
 * 给定 target = 20，返回 false。
 */
public class SearchMatrix {
    public static void main(String[] args) {
        int[][] matrix = new int[][]{
                {1,  4,  7,  11, 15},
                {2,  5,  8,  12, 19},
                {3,  6,  9,  16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}};

        int[][] matrix2 = new int[][]{{-5}};

        System.out.println(searchMatrix2(matrix2, -5));

    }


    /**
     * 递归分治
     *
     * 思路:
     * 由于矩阵每行每列都是递增的，所以可以从左上到右下遍历矩阵的主对角线来将矩阵切分为四个区域
     * 当对角线的元素matrix[i + 1][i + 1]等于目标值target 返回true
     * 当最对角线matrix[0][0] 都大于 target时,返回false
     * 当对角线最下方的元素都比target小时，返回false
     * 当matrix[i][i]< target < matrix[i + 1][i + 1]时，
     *    递归寻找由这两个元素划分出来的四个区域中右上和左下的区域
     *
     * @param matrix
     * @param target
     * @return
     */
    public static boolean searchMatrix(int[][] matrix, int target) {
        // 前一个是行数为0，后一个是列数为0
        if (matrix.length == 0 || matrix[0].length == 0)
            return false;
        return searchMatrix(matrix, target, 0, 0, matrix.length - 1, matrix[0].length - 1);

    }

    /**
     * 分治优化
     *
     * 思路:
     * 定义两个指针row = 0,column = n分别代表行列指针
     * 由于矩阵每行每列都是递增的，所以可以从右上向前遍历
     * 当target等于当前元素时 返回true
     * 当target小于当前元素时，column--
     * 当target大于当前元素时，row++
     *
     *
     *
     * @param matrix
     * @param target
     * @return
     */
    public static boolean searchMatrix2(int[][] matrix, int target) {
        // 前一个是行数为0，后一个是列数为0
        if (matrix.length == 0 || matrix[0].length == 0)
            return false;
        int curRow = 0, curColumn = matrix[0].length - 1;

        while (curRow < matrix.length && curColumn >= 0) {
            if (matrix[curRow][curColumn] == target){
                return true;
            } else if (matrix[curRow][curColumn] > target) {
                curColumn--;
            } else {
                curRow++;
            }

        }
        return false;
    }

    private static boolean searchMatrix(int[][] matrix, int target, int startRow, int startColumn, int endRow, int endColumn) {
        // 递归结束条件
        if (startRow > endRow || startColumn > endColumn)// 元素个数小于1
            return false;
        if (matrix[startRow][startColumn] > target)// 矩阵最小元素大于目标值
            return false;


        // 函数主体功能 在对⻆角线上查找元素 、分解问题、递归求解、合并
        // 矩阵的对角线长度
        int diagonalLength = Math.min(endRow - startRow + 1, endColumn - startColumn + 1);
        for (int i = 0; i < diagonalLength; i++) {
            // 对角线元素等于target值，直接返回true
            if (matrix[startRow + i][startColumn + i] == target)
                return true;

            if ((i == (diagonalLength - 1)) ||
                    matrix[startRow + i + 1][startColumn + i + 1] > target) {
                // 划分的子区域进行递归调用
                //  等价关系式：f(m)=f(m1)||f(m2) m1、m2为划分后待查找的⼦子矩阵
                return searchMatrix(matrix, target, startRow,
                        startColumn + i + 1, startRow + i, endColumn) // 右上区域
                        || searchMatrix(matrix, target, startRow + i + 1, startColumn, // 左下区域
                        endRow, startColumn + i);
            }
        }
        return false;
    }
}
